Dimostrazioni del piccolo teorema di Fermat

Qui di seguito troverete una collezione di dimostrazioni del Piccolo teorema di Fermat:

$\,a^{p}\equiv a$ (mod $p$)

per ogni numero primo $p$ ed ogni intero $a$.

Semplificazione

È da notare che basta provare

$a^{p-1}\equiv 1{\pmod {p}}$

per ogni intero $a$ primo con $p$. Moltiplicando ambo i membri dell'ultima espressione per $a$ si ottiene la versione esposta a inizio pagina del teorema. Se $a$ non fosse primo con $p$ allora $a^{p}\equiv 0\equiv a{\pmod {p}}$ ed il teorema risulterebbe vero in ogni caso.

Dimostrazione sfruttando i multipli del numero intero

Sfruttando la semplificazione proposta nel precedente paragrafo, si considerino i multipli di $a$ che vanno da $a$ stesso fino a $(p-1)a$. Nessuno di questi multipli può dare resto $0$ diviso per $p$ perché né $p-1$ né $a$ sono multipli interi di $p$. Inoltre non può esistere una coppia di questi multipli che sia congrua modulo $p$, perché, se fosse per esempio

$ra\equiv sa{\pmod {p}}$

si avrebbe

$(r-s)a\equiv 0{\pmod {p}}$

Ma questo è impossibile, perché allora $p$ dovrebbe dividere uno dei due fattori. Ma $a$ è primo con $p$, e $r-s$, essendo $r$ ed $s$ numeri naturali compresi tra $1$ e $p$, è $(r-s)<p$. Per cui i multipli considerati hanno un resto nella divisione per $p$ differente per ciascuno di essi, e differente da $0$. Siccome consideriamo $p-1$ multipli, tali multipli devono essere necessariamente congrui (modulo $p$) ai numeri $1,2,3,\dots ,p-1$ in un certo ordine. Ne segue, per il prodotto di tutti questi multipli:

$a(2a)(3a)...(p-1)a=1\cdot 2\cdot 3\cdot \dots \cdot (p-1)a^{p-1}\equiv 1\cdot 2\cdot 3\cdot \dots \cdot (p-1){\pmod {p}}$

da cui, ponendo $K=1\cdot 2\cdot 3\cdot \dots \cdot (p-1)$, si ha

$K(a^{p-1}-1)\equiv 0{\pmod {p}}.$

Dato che $p$ è primo, l'unico modo affinché ciò avvenga è che o K o il secondo fattore sia divisibile per $p$. (con $p$ primo le classi di modulo n costituiscono un dominio di integrità).

Ma $K$ non è divisibile per $p$, perché non lo è nessuno dei suoi fattori; quindi deve essere

$a^{p-1}-1\equiv 0{\pmod {p}}.$

Dimostrazione sfruttando il Teorema di Eulero

Questo teorema può essere visto come un corollario del Teorema di Eulero. Osserviamo che $\,\phi (p)=p-1$ per ogni $p$ primo (dove $\phi$ indica la Funzione φ di Eulero). Per il Teorema di Eulero abbiamo che $\,a^{\phi (p)}\equiv 1$ (mod $p$) per ogni $a$. Si ha quindi la tesi.

Dimostrazione come corollario del teorema di Lagrange sui gruppi

L'insieme dei numeri interi positivi minori di $p$ costituisce un gruppo (che chiameremo $G$) rispetto alla moltiplicazione modulo $p$, avente come elemento identità il numero $1$. L'ordine (ossia il numero di elementi) di questo gruppo, che indichiamo come $o(G)$, è esattamente $p-1$. Se $a\in G$, si definisce ordine di $a$ il più piccolo intero positivo $m$ tale che $a^{m}$ sia l'identità. Un'immediata conseguenza del teorema di Lagrange sui gruppi afferma che $o(a)$ divide $o(G)$. Da questo segue che $a^{o(G)}$ dà necessariamente l'elemento identità del gruppo, essendo $a^{o(G)}=a^{k(o(a))}$. Nel caso specifico, quindi, risulterà $a^{p-1}\equiv 1{\pmod {p}}$.

Dimostrazione per induzione

Dimostriamo il teorema con $a\geq \ 1$ per induzione su $a$: per $a=1$ allora $1=1^{p}\equiv 1$. Sia vera la tesi per $a$, cioè $a^{p}\equiv a$ (mod $p$). Vogliamo mostrare che essa è vera per $a+1$. Per il teorema binomiale, abbiamo che

$(a+1)^{p}=\sum _{i=0}^{p}{p \choose i}a^{i}.$

I coefficienti binomiali ${p \choose i}={\frac {p!}{i!(p-i)!}}$ sono tutti numeri interi e quindi, dato che possono essere riscritti come ${\frac {p}{i}}{p-1 \choose i-1}$ per $0<i<p$, si ha che ${p}{p-1 \choose i-1}$ è divisibile per $i$ ($0<i<p$); in particolare (dal momento che $p$ è un numero primo e quindi $i$ non divide $p$) pure il fattore binomiale residuo ${p-1 \choose i-1}$, anch'esso intero, è multiplo di $i$ ($0<i<p$); pertanto ${\frac {p-1 \choose i-1}{i}}$ è pure un numero intero; ne segue che i coefficienti binomiali ${p \choose i}$ sono (per $0<i<p$) divisibili per $p$ (essendo, come appena dimostrato, ${\frac {p \choose i}{p}}={\frac {p-1 \choose i-1}{i}}$ un numero intero) ossia:

${p \choose i}\equiv 0{\pmod {p}},\qquad 0<i<p.$

Otteniamo quindi che

$(a+1)^{p}=\sum _{i=0}^{p}{p \choose i}a^{i}\equiv a^{p}+1\equiv a+1{\pmod {p}},$

dove la prima equivalenza ($\equiv$) si ottiene eliminando dai $p+1$ addendi della sommatoria tutti quelli (dal secondo al penultimo) per cui $0<i<p$ (essendo tutti, come abbiamo dimostrato, divisibili per $p$) e la seconda (ultima) equivalenza è data dall'ipotesi di induzione. Si ha la tesi.

Se $a$ fosse negativo, allora $-a$ è positivo e per quanto detto sopra

$(-a)^{p}\equiv -a{\pmod {p}},$

ma $(-a)^{p}=(-1)^{p}a^{p}$. Se $p$ è dispari allora $(-1)^{p}=-1$ e quindi otteniamo $-a^{p}\equiv -a{\pmod {p}}$ che implica la tesi (moltiplicando per $-1$ entrambi i membri), altrimenti l'unico primo pari è $p=2$ ma in tal caso $-1\equiv 1{\pmod {2}}$ e quindi

$(-a)^{2}=a^{2}\equiv -a\equiv a{\pmod {2}}.$